import java.util.ArrayList;
import java.util.*;
import java.lang.String;
public class Binarytree {
    //节点
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    //创建一个二叉树
    public TreeNode creatTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        TreeNode E = new TreeNode('E');


        A.left = B;
        A.right = F;
        B.left = C;
        B.right = D;
        C.left = E;
        F.left = G;
        F.right = H;
        return A;//不要忘了返回根节点
    }

    //前序遍历
    public void preOrder(TreeNode root) {
        if (root == null) return;
        System.out.printf(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public void preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                System.out.print(cur.val + " ");
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }

    //中序遍历
    public void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.printf(root.val + " ");
        inOrder(root.right);
    }

    public void inorderTraversal(TreeNode root) {
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.right;
        }
    }

    //后序遍历
    public void PostOrder(TreeNode root) {
        if (root == null) return;
        PostOrder(root.left);
        PostOrder(root.right);
        System.out.printf(root.val + " ");
    }
    //二叉树的后序非递归遍历
    public void postorderTraversal(TreeNode root) {
        TreeNode top = null;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while(!stack.isEmpty() || root!=null ){
            while(root!=null){//把root的左树全入栈直到root为null
                stack.push(root);
                root = root.left;
            }
            top = stack.peek();
            if(top.right == null||top.right ==pre){//top右树为null或者root的右树为上个打印的树
                System.out.printf(root.val + " ");
                stack.pop();
                if(top.right!=pre){
                    root = top.right;
                }
                pre = top;
            }else{
                root = top.right;
            }
        }
    }
    //层序遍历

    //获取二叉树所有节点数（遍历思路）
    public List<Character> preOrderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if (root == null) return list;//if(root == null) return null;
        list.add(root.val);

        List<Character> leftTree = preOrderTraversal(root.left);
        list.addAll(leftTree);

        List<Character> rightTree = preOrderTraversal(root.right);
        list.addAll(rightTree);

        return list;
    }

    //获取二叉树的所有节点数(遍历二叉树)
    public static int usedsize;

    public void size1(TreeNode root) {
        if (root == null) return;

        usedsize++;
        size1(root.left);
        size1(root.right);
    }

    //获取二叉树的所有节点（子问题解决）
    public int size2(TreeNode root) {
        if (root == null) return 0;

        int A = size2(root.left);
        int B = size2(root.right);
        return A + B + 1;
    }

    //获取二叉树的叶子节点数
    public static int leaveSize;

    public void LevelNodeCount1(TreeNode root) {
        if (root == null) return;

        if (root.right == null && root.left == null) leaveSize++;

        LevelNodeCount1(root.left);
        LevelNodeCount1(root.right);

    }

    //获取二叉树的叶子节点数（子问题解决）
    public int LevelNodeCount2(TreeNode root) {
        if (root == null) return 0;

        if (root.left == null && root.right == null) return 1;

        int leftCount = LevelNodeCount2(root.left);
        int rightCount = LevelNodeCount2(root.right);
        return leftCount + rightCount;
    }

    //获取二叉树的深度（子问题解决）
    public int TreeHight(TreeNode root) {

        if (root == null) return 0;
        int treeLeft = TreeHight(root.left);
        int treeRight = TreeHight(root.right);

        return Math.max(treeLeft, treeRight) + 1;

    }

    //查找二叉树中的某个值
    public TreeNode findVal(TreeNode root, char val) {
        if (root == null) return null;

        if (root.val == val) return root;

        TreeNode leftT = findVal(root.left, val);
        if (leftT != null) {
            return leftT;
        }
        TreeNode rightT = findVal(root.right, val);
        if (rightT != null) {
            return rightT;
        }
        return null;
    }

    //获取二叉树第K层节点数
    public int getLevelNodeCount(TreeNode root, int k) {
        if (root == null) return 0;

        if (root != null && k == 1) {
            return 1;
        }
        int leftCount = getLevelNodeCount(root.left, k - 1);
        int rightCount = getLevelNodeCount(root.right, k - 1);
        return leftCount + rightCount;
    }
    //判断一个数是不是完全二叉树
    /*public boolean isCompletsTree(TreeNode root){
        if(root == null) return
    }*/

    //层序遍历
    //反转一个二叉树
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    //检查两个二叉树是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //检测结构是否相同
        if (p != null && q == null || p == null && q != null) {
            return false;
        }
        if (p == null && q == null) {
            return true;
        }
        //检测值是否相等
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    //检查该二叉树是不是对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        TreeNode L = root.left;
        TreeNode R = root.right;
        return isSymmetricChild(L, R);
    }

    public boolean isSymmetricChild(TreeNode p, TreeNode q) {
        //检测结构是否对称
        if (p == null && q != null || p != null && q == null) {
            return false;
        }
        if (p == null && q == null) {
            return true;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSymmetricChild(p.left, q.right) && isSymmetricChild(p.right, q.left);
    }

    //检查一棵树是不是另一颗树的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        if (root.val == subRoot.val) {
            if (isSameTree(root, subRoot)) {
                return true;
            }
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    //根据前序遍历和中序遍历创建一颗子树
    public int preIndex;

    public TreeNode buildTree1(String preorder, String inorder) {
        return buildTreeChild1(preorder, inorder, 0, inorder.length() - 1);
    }

    public TreeNode buildTreeChild1(String preorder, String inorder, int inbegin, int inend) {
        //表明递归结束
        if (inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(preorder.charAt(preIndex));
        int rootIndex = find(inorder, inbegin, inend, preorder.charAt(preIndex));
        preIndex++;
        root.left = buildTreeChild1(preorder, inorder, inbegin, rootIndex - 1);
        root.right = buildTreeChild1(preorder, inorder, rootIndex + 1, inend);
        return root;
    }

    public int find(String inorder, int inbegin, int inend, int k) {
        int i = inbegin;
        while (i <= inend) {
            if (inorder.charAt(i) == k) {
                return i;
            }
            i++;
        }
        return -1;
    }

    //根据后序遍历和中序遍历创建一颗二叉树
    public int postIndex;

    public TreeNode buildTree2(String inorder, String postorder) {
        return buildTreeChild2(inorder, postorder, 0, inorder.length() - 1);
    }

    public TreeNode buildTreeChild2(String inorder, String postorder, int inbegin, int inend) {
        if (inbegin > inend) {
            return null;
        }

        TreeNode root = new TreeNode(postorder.charAt(postorder.length() - 1 - postIndex));
        int rootIndex = find(inorder, inbegin, inend, postorder.charAt(postorder.length() - 1 - postIndex));
        postIndex++;
        root.right = buildTreeChild2(inorder, postorder, rootIndex + 1, inend);
        root.left = buildTreeChild2(inorder, postorder, inbegin, rootIndex - 1);
        return root;
    }

    //二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode rootL = lowestCommonAncestor(root.left, p, q);
        TreeNode rootR = lowestCommonAncestor(root.right, p, q);
        if (rootL != null && rootR != null) {
            return root;
        } else if (rootL != null) {
            return rootL;
        } else {
            return rootR;
        }
    }

    //层序遍历，从下往上
    public List<List<Character>> levelOrderBottom(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Character>> lists = new ArrayList<>();
        if (root != null) {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            List<Character> list = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode tmp = queue.poll();
                list.add(tmp.val);
                if (tmp.left != null) {
                    queue.add(tmp.left);
                }
                if (tmp.right != null) {
                    queue.add(tmp.right);
                }
            }
            lists.add(list);
        }
        Collections.reverse(lists);
        return lists;
    }

    //层序遍历，从上到下
    public List<List<Character>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Character>> lists = new ArrayList<>();
        if (root != null) {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            List<Character> list = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode top = queue.poll();
                list.add(top.val);
                if (top.left != null) {
                    queue.add(top.left);
                }
                if (top.right != null) {
                    queue.add(top.right);
                }
            }
            lists.add(list);
        }
        return lists;
    }
    //根据二叉树创建字符串
    private StringBuilder sb;
    public String tree2str(TreeNode root) {
        sb = new StringBuilder();
        dfs(root);
        return sb.toString();
    }

    private void dfs(TreeNode node) {
        if (node != null) {
            sb.append(node.val);
            boolean hasLeft = node.left != null || node.right != null, hasRight = node.right != null;
            if (hasLeft) {
                sb.append("(");
                dfs(node.left);
                sb.append(")");
            }
            if (hasRight) {
                sb.append("(");
                dfs(node.right);
                sb.append(")");
            }
        }
    }
}



